A machine can be configured to generate, compress, decompress, store, communicate, or otherwise process computer graphics that represent two-dimensional (2D) or three-dimensional (3D) objects. As one example, the machine may generate, compress, decompress, or otherwise process a mesh that represents the 3D surfaces of a 3D object as a set of connected polygons (e.g., triangles), which are in turn represented by lists of vertices and connections among such vertices. The 3D positions of the vertices are known as geometry, and the connections among them are known as connectivity.
To compress a mesh, both geometry information and connectivity information are compressed. Time-varying surfaces are known as dynamic or animated meshes. For dynamic meshes, the geometry information also includes the motion information. For meshes, spatial random access is generally achieved by breaking a mesh into regions and compressing each one separately. Breaking a mesh into regions also allows the mesh to be processed in parallel or out-of-core. Progressive mesh compression is generally achieved by starting with a coarse mesh and either subdividing the faces or splitting the vertices, resulting in a sequence of increasingly fine meshes. In some scenarios, the finest mesh output from a decoder is constrained to have connectivity identical to the mesh that was input to an encoder; in other scenarios, it is acceptable to “remesh” the input mesh.
As another example, the machine may generate, compress, decompress, or otherwise process voxels that represent the 3D surfaces of the 3D object. Voxels are particularly popular in the robotics community. A voxel is said to be occupied if a scanner (e.g., a light detection and ranging (LIDAR) scanner) determines that the voxel has a surface passing through it. Thus, a set of occupied voxels can be considered a representation of a surface. Such a set of occupied voxels is sparse in 3D, because the voxels lie only on a surface. In robotics, the occupied voxels are said to lie on an occupancy grid.
A Sparse Voxel Octree (SVO) is a data structure (e.g., an octree) that represents a sparse set of occupied voxels. In an SVO, the root node is identified with a cube in space. If the cube is occupied (i.e., if it contains an occupied voxel), then the cube is subdivided into eight sub-cubes. Each sub-cube may, in turn, be occupied or not. Those sub-cubes that are occupied are identified with an 8-bit byte, or occupancy code, for the root node. Occupied sub-cubes are recursively sub-divided until their corresponding nodes in the octree reach a certain level or depth of the octree.
As a further example, the machine may generate, compress, decompress, or otherwise process a function that represents a 3D surface implicitly. Suppose ƒ(x) is a real scalar function of x∈3, and suppose c is a real constant. Then the set of all x such that ƒ(x)=c implicitly defines a surface. Thus any representation of ƒ(x) is a representation of the surface. One option for ƒ(x) is the distance function,
            f      ⁡              (        x        )              =                  min                  y          ∈          S                    ⁢                                x          -          y                              ,which equals 0 if and only if x∈S, where S is the surface. Thus ƒ(x)=0 defines the surface S.
Another option for ƒ(x) is the signed distance function, which can be defined as follows. With S as the surface, let
      min          y      ∈      S        ⁢                x      -      y          be the distance between x and S, let
      y    x    =      arg    ⁢                  min                  y          ∈          S                    ⁢                                x          -          y                            be the closest point to x on S, let n(yx) be the surface normal at yx, and let sgn((yx−x)·n(yx)) be the sign of the dot product between yx−x and n(yx), which is typically negative outside the surface and positive inside the surface. Then the signed-distance function is
            f      ⁡              (        x        )              =                  sgn        ⁡                  (                                    (                                                y                  x                                -                x                            )                        ·                          n              ⁡                              (                                  y                  x                                )                                              )                    ⁢                        min                      y            ∈            S                          ⁢                                        x            -            y                                          ,and ƒ(x)=0 defines the surface S. Another option for ƒ(x) is the occupancy probability, that is, the probability that the point x lies on or inside the surface of an object. In this case, ƒ(x)=½ may be used to define the surface S.